В одном из вариантов поиска в глубину, называемом поиском с возвратами, используется еще меньше памяти. При поиске с возвратами каждый раз формируется только один преемник, а не все преемники; в каждом частично развернутом узле запоминается информация о том, какой преемник должен быть сформирован следующим. Таким образом, требуется только 0{т) памяти, а не 0{bm). При поиске с возвратами применяется еще один прием, позволяющий экономить память (и время); идея его состоит в том, чтобы при формировании преемника должно непосредственно модифицироваться описание текущего состояния, а не осуществляться его предварительное копирование. При этом потребность в памяти сокращается до объема, необходимого для хранения только одного описания состояния и О(т) действий. Но для успешного применения данного приема нужно иметь возможность отменять каждую модификацию при возврате, выполняемом для формирования следующего преемника. При решении задач с объемными описаниями состояния, таких как роботизированная сборка, применение указанных методов модификации состояний становится важнейшим фактором успеха.

Недостатком поиска в глубину является то, что в нем может быть сделан неправильный выбор и переход в тупиковую ситуацию, связанную с прохождением вниз по очень длинному (или даже бесконечному) пути, притом что другой вариант мог бы привести к решению, находящемуся недалеко от корня дерева поиска. Например, на рис. 3.8 поиск в глубину потребовал бы исследования всего левого поддерева, даже если бы целевым узлом был узел С, находящийся в правом поддереве. А если бы целевым узлом был также узел J, менее приемлемый по сравнению с узлом С, то поиск в глубину возвратил бы в качестве решения именно его; это означает, что поиск в глубину не является оптимальным. Кроме того, если бы левое поддерево имело неограниченную глубину, но не содержало бы решений, то поиск в глубину так никогда бы и не закончился; это означает, что данный алгоритм — не полный. В наихудшем случае поиск в глубину формирует всеузлов в дереве поиска, где т — максимальная глубина любого узла. Следует отметить, что т может оказаться гораздо больше по сравнению с d (глубиной самого поверхностного решения) и является бесконечным, если дерево имеет неограниченную глубину.